#ifndef _BST_HPP_
#define _BST_HPP_

#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;

template<typename T>
void random_shuffle(vector<T> &target){
    int len=target.size();
    for(int i=len-1;i>0;i--){
        int j=rand()%i;
        swap(target[i],target[j]);
    }
}

template <typename T>
class bst_tree{
    private:

    struct node{
        T element;
        int num;
        node *left;
        node *right;
    };

    inline void create_node(node *target, const T & theElement, node *ls, node *rs){
        target->element=theElement;
        target->left=ls; target->right=rs;
        target->num=1;
    }

    node *root;
    bool isempty;

    void insert(const T & object){
        if(isempty){
            create_node(root,object,nullptr,nullptr);
            isempty=false;
        }
        else{
            node *index=root;
            while(object!=index->element){
                if(object<index->element&&index->left!=nullptr) index=index->left;
                else if(object>index->element&&index->right!=nullptr) index=index->right;
                else break;
            }
            if(object==index->element) index->num++;
            else if(object<index->element){
                index->left= new node;
                create_node(index->left,object,nullptr,nullptr);
            }else{
                index->right = new node;
                create_node(index->right,object,nullptr,nullptr);
            }
        }
    }
    void erase(node *theNode){
        if(theNode->left==nullptr||theNode->right==nullptr){
            delete theNode;
            return;
        }
        if(theNode->left!=nullptr) erase(theNode->left);
        if(theNode->right!=nullptr) erase(theNode->right); 
    }
    const T& find_min(node* theNode){
        if(theNode->left==nullptr) return theNode->element;
        else find_min(theNode->left);
    }
    const T& find_max(node* theNode){
        if(theNode->right==nullptr) return theNode->element;
        else find_max(theNode->right);
    }
    void mid_print(node *theNode){
        if(theNode->left!=nullptr) mid_print(theNode->left);
        cout<<theNode->element<<' ';
        if(theNode->right!=nullptr) mid_print(theNode->right);
        return;
    }
    void mid_out(node *theNode,vector<T>& target){
        if(theNode->left!=nullptr) mid_out(theNode->left,target);
        for(int i=1;i<=theNode->num;i++) target.push_back(theNode->element);
        if(theNode->right!=nullptr) mid_out(theNode->right,target);
        return;
    }

    public:
    bst_tree(){
        root=new node;
        root->left=root->right=nullptr;
        isempty=true;
    }
    ~bst_tree(){
        erase(root);
    }
    bool tree_empty() const{
        return isempty;
    }
    void bst_insert(const T& object){
        insert(object);
    }
    const T& min_ele(){
        if(tree_empty()){
            cout<<"Error! BST is empty!"<<endl;
            return root->element;
        }
        return find_min(root);
    }
    const T& max_ele(){
        if(tree_empty()){
            cout<<"Error! BST is empty!"<<endl;
            return root->element;
        }
        return find_max(root);
    }
    void bst_midprint(){
        mid_print(root);
    }
    void bst_midout(vector<T>& _target){
        mid_out(root,_target);
    }  
};

template <typename T>
void BST_sort(vector<T>& _data){
        bst_tree<T> tree;
        for(unsigned long int i=0;i<_data.size();i++) tree.bst_insert(_data[i]);
        int size=_data.size();
        for(int i=0;i<size;i++) _data.pop_back();
        tree.bst_midout(_data);
}

template<typename T>
void Randomized_BST_sort(vector<T>& _data){
    random_shuffle(_data);
    BST_sort(_data);
}



#endif